package codingforgreat.lchot150;

import java.util.ArrayList;
import java.util.List;

public class Lc094 {
 public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;

     TreeNode() {
     }

     TreeNode(int val) {
         this.val = val;
     }

     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
    public List<Integer> inorderTraversal(TreeNode root) {
        TreeNode cur = root;
        TreeNode mostR = null;
        List<Integer> res = new ArrayList<>();
        while(cur != null){
            mostR = cur.left;
            if(mostR != null){
                while(mostR.right != cur && mostR.right != null){
                    mostR = mostR.right;
                }

                if(mostR.right == null){
                    mostR.right = cur;
                    cur = cur.left;
                    continue;
                }
                if(mostR.right == cur){
                    res.add(cur.val);
                    mostR.right = null;
                }

            }else{
                res.add(cur.val);
            }
            cur = cur.right;
        }
        return res;
    }
}
